package linkedList;

import queue.Queue;

public class LinkedListQueue <E> implements Queue <E>{

	/**
	 * 使用链表实现队列
	 * @author Administrator
	 *
	 */
	private class Node{
		public E e;
		public Node next;
		
		public Node(E e,Node next) {
			this.e = e;
			this.next = next;
		}
		
		public Node(E e) {
			this(e,null);
		}
		
		public Node() {
			this(null,null);
		}
		
		@Override
		public String toString() {
			return e.toString();
		}
	}
	
	private Node head,tail;
	private int size;
	
	/**
	 * 入队时通过尾巴插入，因为尾巴删除不容易
	 */
	@Override
	public void enqueue(E e) {
		Node node = new Node(e);
		if(size == 0) {
			head = node;
			tail = node;
		} else {
			tail.next = node;
			tail = tail.next;
			node.next = null;
		}
		size++;
	}
	@Override
	public E dequeue() {
		/**
		 * 出队:从头部出队，因为头部删除元素比较容易
		 */
		if(isEmpty())
			throw new IllegalArgumentException();
		Node retNode = head;
		head = head.next;
		retNode.next = null;
		
		if(head == null)
			tail = null;
		size--;
		return retNode.e;
	}
	@Override
	public E getFront() {
		if(isEmpty())
			throw new IllegalArgumentException();
		return head.e;
	}
	@Override
	public int getSize() {
		
		return size;
	}
	@Override
	public boolean isEmpty() {
		
		return size == 0;
	}
	
	
	@Override
	public String toString() {
		StringBuilder res = new StringBuilder();
		res.append("Queue: front");
		
		Node cur = head;
		while(cur != null) {
			res.append(cur + "->");
			cur = cur.next;
		}
		res.append("NULL tail");
		return res.toString();
	}
	
	public static void main(String[] args) {
		LinkedListQueue<Integer> queue = new LinkedListQueue<>();
		for(int i = 0 ; i < 5 ; i++) {
			queue.enqueue(i);
			System.out.println(queue);
		}
		queue.dequeue();
		System.out.println(queue);
	}
}
